#include "list.h"

#include <assert.h>
#include <stdlib.h>

struct _listnode
{
	struct _listnode *left;
	struct _listnode *right;
	void *data; //数据
};
//列表的实现
struct _list
{
	ListNode *head;
	ListNode *end;
	int length;
	void *(*listMalloc)(size_t size);
	void (*listFree)(void *ptr);
}
;
struct _listcursor
{
	ListNode *pnode;
};

List *ListInit()
{
	List *list;
	list = (List*) malloc(sizeof(List));
	list->length = 0;
	list->head = 0;
	list->end = 0;
	list->listFree = free;
	list->listMalloc = malloc;
	return list;
}

//从末尾操作插入
void *ListPush(List *plist, void *data)
{
	//插入一个节点
	assert(plist);
	assert(data);

	ListNode *pnode;
	pnode = (ListNode*) (plist->listMalloc(sizeof(ListNode)));
	pnode->data = data;
	pnode->left = plist->end;
	pnode->right = 0;
	if (plist->end) {
		plist->end->right = pnode;
	}
	else {
		plist->head = pnode;
	}
	plist->end = pnode;
	plist->length++;
	return pnode->data;
}
void *ListPop(List *plist)
{
	assert(plist);
	if (plist->length == 0) {
		return 0;
	}
	ListNode *pnode;
	pnode = plist->end;
	plist->end = plist->end->left;
	if (plist->end == 0) {
		plist->head = 0;
	}
	else {
		plist->end->right = 0;
	}
	void *pdata;
	pdata = pnode->data;
	pnode->left = 0;
	pnode->right = 0;
	plist->listFree(pnode);
	plist->length--;
	return pdata;
}
//从前端操作插入
void *ListImport(List *plist, void *data)
{
	//插入一个节点
	assert(plist);
	assert(data);
	ListNode *pnode;
	pnode = (ListNode*) (plist->listMalloc(sizeof(ListNode)));
	pnode->data = data;
	pnode->right = plist->head;
	pnode->left = 0;
	if (plist->head) {
		plist->head->left = pnode;
	}
	else {
		plist->end = pnode;
	}
	plist->head = pnode;
	plist->length++;
	return pnode->data;
}
void *ListExport(List *plist)
{
	assert(plist);
	if (plist->length == 0) {
		return 0;
	}
	ListNode *pnode;
	pnode = plist->head;
	plist->head = plist->head->right;
	if (plist->head == 0) {
		plist->end = 0;
	}
	else {
		plist->head->left = 0;
	}
	pnode->left = 0;
	pnode->right = 0;
	plist->length--;
	void *pdata;
	pdata = pnode->data;
	plist->listFree(pnode);
	return pdata;
}
//任意位置操作
void *ListInsert(List *plist, void *data, ListCursor *pcursor)
{
	assert(plist);
	assert(data);
	if (pcursor == 0) {
		return ListImport(plist, data);
	}
	if (pcursor->pnode == 0) {
		return ListImport(plist, data);
	}
	if (pcursor->pnode->left == 0) {
		pcursor->pnode = 0;
		return ListImport(plist, data);
	}
	if (pcursor->pnode->right == 0) {
		ListPush(plist, data);
		pcursor->pnode = plist->end;
		return plist;
	}
	ListNode *pnode;
	pnode = (ListNode*) (plist->listMalloc(sizeof(ListNode)));
	pnode->data = data;
	pnode->left = pcursor->pnode;
	pnode->right = pcursor->pnode->right;
	pcursor->pnode->right->left = pnode;
	pcursor->pnode->right = pnode;
	pcursor->pnode = pnode;
	plist->length++;
	return pnode->data;
}

void *ListRemove(List *plist, void *data)
{
	assert(plist);
	assert(data);
	if (plist->length == 0) {
		return 0;
	}
	ListNode *pnode;
	pnode = plist->head;
	while (pnode) {
		if (pnode->data == data) {
			//删除该数据
			if (pnode->left == 0) {
				return ListExport(plist);
			}
			if (pnode->right == 0) {
				return ListPop(plist);
			}
			pnode->left->right = pnode->right;
			pnode->right->left = pnode->left;
			pnode->left = 0;
			pnode->right = 0;
			plist->listFree(pnode);
			plist->length--;
			return data;
		}
		pnode = pnode->right;
	}
	return 0;

}
void *ListCursorRemove(List *plist, ListCursor *pcursor)
{
	assert(plist);
	assert(pcursor);
	if (plist->length == 0) {
		return 0;
	}
	if (pcursor->pnode == 0) {
		return ListExport(plist);
	}
	if (pcursor->pnode->left == 0) {
		return ListExport(plist);
	}
	if (pcursor->pnode->right == 0) {
		return ListPop(plist);
	}
	pcursor->pnode->left->right = pcursor->pnode->right;
	pcursor->pnode->right->left = pcursor->pnode->left;
	void *pdata;
	ListNode *pnode;
	pdata = pcursor->pnode->data;
	pnode = pcursor->pnode;
	pcursor->pnode = pcursor->pnode->right;
	pnode->left = 0;
	pnode->right = 0;
	plist->listFree(pnode);
	plist->length--;
	return pdata;
}
List *ListEmpty(List *plist)
{
	assert(plist);
	while (plist->length) {
		ListPop(plist);
	}
	plist->end = 0;
	plist->head = 0;
	plist->length = 0;
	return plist;
}

int ListLength(List *plist)
{
	assert(plist);
	return plist->length;
}

void *ListForeach(List *plist, ListCursor *pcursor)
{
	assert(plist);
	assert(pcursor);

	if (pcursor->pnode == 0) {
		pcursor->pnode = plist->head;
		if (pcursor->pnode) {
			return pcursor->pnode->data;
		}
		return 0;
	}
	pcursor->pnode = pcursor->pnode->right;
	if (pcursor->pnode) {
		return pcursor->pnode->data;
	}
	return 0;
}

void ListAllocator(List *plist, void *(*pmalloc)(size_t size),
		void (*pfree)(void *pdata))
{
	assert(plist);
	plist->listMalloc = pmalloc;
	plist->listFree = pfree;
}

ListCursor *ListGetCursor(List *plist)
{
	assert(plist);
	ListCursor *pcursor;
	pcursor = (ListCursor*) malloc(sizeof(ListCursor));
	pcursor->pnode = 0;
	return pcursor;
}
